package com.zhangxiaofanfan.hotcode.first;

import java.util.Arrays;

/**
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode079 {
    public static void main(String[] args) {
        HotCode079 hotCode = new HotCode079();
        int[] nums = {2,3,0,1,4};
        System.out.println(hotCode.jump(nums));
    }

    public int jump(int[] nums) {
        int curIndex = 0, arriveIndex;
        int[] step = new int[nums.length];
        Arrays.fill(step, Integer.MAX_VALUE);
        step[0] = 0;
        while (curIndex < nums.length) {
            if (step[curIndex] == Integer.MAX_VALUE) {
                curIndex++;
                continue;
            }
            arriveIndex = curIndex + nums[curIndex];
            for (int i = curIndex; i <= arriveIndex && i < nums.length; i++) {
                step[i] = Math.min(step[i], step[curIndex] + 1);
                if (i == nums.length - 1) {
                    return step[step.length - 1];
                }
            }
            curIndex++;
        }
        return step[step.length - 1] == Integer.MAX_VALUE ? -1 : step[step.length - 1];
    }

}
